package com.mdnote.practice.plus_search.a_start;

import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * @author Rhythm-2019
 * @date 2020/10/3
 * @description 二进制矩阵中的最短路径
 */
public class LeetCode1091 {

     private int[][] grid;

     private int[][] direction = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

    public static void main(String[] args) {
        LeetCode1091 leetCode1091 = new LeetCode1091();
        int[][] board = {
                {0, 0, 0},
                {1, 1, 0},
                {1, 1, 0}
        };
//        int[][] board = {
//                {0, 1},
//                {1, 0},
//        };
        System.out.println(leetCode1091.shortestPathBinaryMatrix(board));
    }

    /**
     * 可以使用A*、BFS、DFS做
     * @param grid
     * @return
     */
    public int shortestPathBinaryMatrix(int[][] grid) {

        if (grid[0][0] == 1 || grid[grid.length - 1][grid[0].length - 1] == 1) {
            return 0;
        }
        this.grid = grid;
//        return _bfs(grid);

        return _astart(grid);
    }

    private int _astart(int[][] grid) {

        if (grid.length == 1) {
            return 1;
        }
        PriorityQueue<Point> queue = new PriorityQueue<>();
        queue.add(new Point(0, 0, 1));
        grid[0][0] = 1;
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int step = grid[point.row][point.column];

            for (int dir = 0; dir < direction.length; dir++) {
                int new_row = point.row + direction[dir][0];
                int new_col = point.column + direction[dir][1];
                if (new_row== grid.length - 1 && new_col == grid[0].length - 1) {
                    return step + 1;
                }
                if (inGrid(new_row, new_col)) {
                    if (grid[new_row][new_col] != 0 && grid[new_row][new_col] <= step + 1) {
                        // 如果下一步的步数比较小，那么就不要覆盖别人的值了
                        continue;
                    }
                    grid[new_row][new_col] = step + 1;
                    queue.offer(new Point(new_row, new_col, step + 1));
                }
            }

        }

        boolean a = false;
        int t = a? 1 : 2;
        return -1;
    }


    private int _bfs(int[][] grid) {

        LinkedList<Point> queue = new LinkedList<>();
        queue.add(new Point(0, 0));

        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point point = queue.removeFirst();
                // 判断是否访问过
                if (grid[point.row][point.column] == 1) {
                    continue;
                }
                // 判断是否到达总店==终点，可以放在下面的for循环种，但是需要排除{{0}}这种情况，且step初始值未1
                if (point.row == grid.length - 1 && point.column == grid[0].length - 1) {
                    return step + 1;
                }
                grid[point.row][point.column] = 1;
                for (int dis = 0; dis < direction.length; dis++) {
                    int new_row = point.row + direction[dis][0];
                    int new_column = point.column + direction[dis][1];
                    if (inGrid(new_row, new_column) && grid[new_row][new_column] == 0) {
                        queue.addLast(new Point(new_row, new_column));
                    }
                }
            }
            step++;
        }
        return -1;
    }

    private boolean inGrid(int row, int column) {
        return row >= 0 && row < grid.length && column >= 0 && column < grid[0].length;
    }


    private class Point implements Comparable<Point> {
        private int row;
        private int column;
        private int weight;

        public Point(int row, int column) {
            this.row = row;
            this.column = column;

        }

        public Point(int row, int column, int step) {
            this.row = row;
            this.column = column;
            this.weight = Math.min(grid.length - 1 - row, grid[0].length - 1 - column) + step;
        }

        @Override
        public int compareTo(Point o) {
            return this.weight - o.weight;
        }
    }
}
